      1  import java.util.List;

      2  import java.util.ArrayList;

      3

      4  /**

      5     A tree in which each node has an arbitrary number of children.

      6  */

      7  public class Tree

      8  {

      9     private Node root;

     10

     11     class Node

     12     {

     13        public Object data;

     14        public List<Node> children;

     15

     16        /**

     17           Computes the size of the subtree whose root is this node.

     18           @return the number of nodes in the subtree

     19        */

     20        public int size()

     21        {

     22           int sum = 0;

     23           for (Node child : children) { sum = sum + child.size(); }

     24           return 1 + sum;

     25        }

     26     }

     27

     28     /**

     29        Constructs an empty tree.

     30     */

     31     public Tree()

     32     {

     33        root = null;

     34     }

     35

     36     /**

     37        Constructs a tree with one node and no children.

     38        @param rootData the data for the root

     39     */

     40     public Tree(Object rootData)

     41     {

     42        root = new Node();

     43        root.data = rootData;

     44        root.children = new ArrayList<Node>();

     45     }

     46

     47     /**

     48        Adds a subtree as the last child of the root.

     49     */

     50     public void addSubtree(Tree subtree)

     51     {

     52        root.children.add(subtree.root);

     53     }

     54

     55     /**

     56        Computes the size of this tree.

     57        @return the number of nodes in the tree

     58     */

     59     public int size()

     60     {

     61        if (root == null) { return 0; }

     62        else { return root.size(); }

     63     }

     64

     65     // Additional methods will be added in later sections.

     66  }